#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
struct Trie{
	#define Trie_maxn 1000 
	#define CharterMax 128
	#define idx(A) (A)
	#define u idx(TpChr)
	
	int ch[Trie_maxn][CharterMax],val[Trie_maxn],cnt=0;
	int TpInd=0;
	char TpChr='\0';
	int cnts = 0;
	
	void init(){
		cnt = 0;
	}
	
	void insert(const char* str){
		int len = strlen(str) ;
		int c = ++cnts;
		TpInd=0;
		for(int i=0;i<len;i++){
			TpChr = str[i];
			if(!ch[TpInd][u]){
				val[TpInd] = 0;
				ch[TpInd][u] = ++cnt;
			}
			TpInd = ch[TpInd][u];
		}
		val[TpInd] = ++cnts;
		return;
	}
	
	int find(const char* str){
		if(str == "")
			return 0;
		int len = strlen(str) ;
		TpInd=0;
		for(int i=0;i<len;i++){
			TpChr = str[i];
			if(!ch[TpInd][u]){
				return -1;
			}
			TpInd = ch[TpInd][u];
		}
		if(!val[TpInd])
			return -1;
		return TpInd;
	}
	
	void dfs(std::string s,int Ind){
		if(val[Ind])
			printf("%s\n",s.c_str());
		for(int i=0;i<CharterMax;i++)
			if(ch[Ind][i])
				dfs(s+char(i),ch[Ind][i]);
	}
	void findstr(const char* str){
		TpInd = 0;
		
		if(str == "")
			TpInd = 0;
		int len = strlen(str) ;
		TpInd=0;
		for(int i=0;i<len;i++){
			TpChr = str[i];
			if(!ch[TpInd][u]){
				return;
			}
			TpInd = ch[TpInd][u];
		}
		
		dfs(str,TpInd);
		return;
	}
	void loadxson(const std::string& str){
		int a[128],top=1;
		a[1] = 0 ;
		for(int i=0;i<str.length();i++){
			printf("%d top:%d chr<%c>\n",i,top,str[i]);
//			printf("pass1\n");
			if(str[i] == '[')
				continue;
			if(str[i] == ']'){
				top--;
				continue;
			}
			
//			printf("pass2\n");
			if(!ch[a[top]][str[i]])
				ch[a[top]][str[i]] = ++cnt;
//			printf("pass3\n");
			if(str[i+1] == '*')
				val[ch[a[top]][str[i]]] = ++cnts,
				i++;
//			printf("pass4\n");
			a[top+1] = ch[a[top]][str[i]];
//			printf("pass4.5\n");
			top++;
//			printf("pass5\n");
		}
		// [a[b[]]]
	}
	std::string toxson(int index = 0){
//		printf("start\n");
		std::string rslt="[";
		for(int i=0;i<CharterMax;i++){
			if(ch[index][i]){
				rslt+=i;
				if(val[ch[index][i]])
					rslt+='*';
				rslt+=toxson(ch[index][i]);
			}		
		}
//		printf("%s\n",rslt.c_str());
		rslt+=']';
		return rslt;
	}
	
	#undef Trie_maxn
	#undef CharterMax
	#undef idx(A)
};
